package main

import "container/list"

type LRUCache struct {
	capacity int
	m        map[int]*list.Element
	l        *list.List
}

func NewCache(cap int) *LRUCache {
	return &LRUCache{capacity: cap, m: make(map[int]*list.Element), l: list.New()}
}

type Pair struct {
	k int
	v interface{}
}

func (c *LRUCache) Set(key int, value interface{}) {
	if e, ok := c.m[key]; ok {
		e.Value = Pair{k: key, v: value}
		c.l.MoveToFront(e)
		return
	} else {
		if len(c.m) == c.capacity {
			e := c.l.Back()
			c.l.Remove(e)
			delete(c.m, e.Value.(Pair).k)
		}

		p := Pair{k: key, v: value}
		newElement := c.l.PushFront(p)
		c.m[key] = newElement
	}
}

func (c *LRUCache) Get(key int) (interface{}, bool) {
	if e, ok := c.m[key]; ok {
		c.l.MoveToFront(e)
		return e.Value.(Pair).v, true
	} else {
		return -1, false
	}
}

func main() {
	c := NewCache(2)
	c.Set(1, 1)
	c.Set(2, 2)
	c.Set(3, 3)
}
